<!DOCTYPE HTML>
<html lang="en" >
    
    <head>
        
        <meta charset="UTF-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <title>各种树 | python 数据结构与算法</title>
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="generator" content="GitBook 2.6.7">
        
        
        <meta name="HandheldFriendly" content="true"/>
        <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
        <meta name="apple-mobile-web-app-capable" content="yes">
        <meta name="apple-mobile-web-app-status-bar-style" content="black">
        <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
        <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">
        
    <link rel="stylesheet" href="../gitbook/style.css">
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-highlight/website.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-search/search.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-fontsettings/website.css">
        
    
    

        
    
    
    <link rel="next" href="../树的实现/B-树.html" />
    
    
    <link rel="prev" href="../剑指offer/剑指offer25-43题.html" />
    

        
    </head>
    <body>
        
        
    <div class="book"
        data-level="2"
        data-chapter-title="各种树"
        data-filepath="树的实现/树的定义.md"
        data-basepath=".."
        data-revision="Mon Jun 10 2019 17:10:15 GMT+0800 (中国标准时间)"
        data-innerlanguage="">
    

<div class="book-summary">
    <nav role="navigation">
        <ul class="summary">
            
            
            
            

            

            
    
        <li class="chapter " data-level="0" data-path="index.html">
            
                
                    <a href="../index.html">
                
                        <i class="fa fa-check"></i>
                        
                        python数据结构与算法
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1" >
            
            <span><b>1.</b> 剑指offer</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.1" data-path="剑指offer/补码.html">
            
                
                    <a href="../剑指offer/补码.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.1.</b>
                        
                        补码
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="剑指offer/剑指offer1-24题.html">
            
                
                    <a href="../剑指offer/剑指offer1-24题.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.2.</b>
                        
                        剑指offer1-24题
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="剑指offer/剑指offer25-43题.html">
            
                
                    <a href="../剑指offer/剑指offer25-43题.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.3.</b>
                        
                        剑指offer25-43题
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter active" data-level="2" data-path="树的实现/树的定义.html">
            
                
                    <a href="../树的实现/树的定义.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.</b>
                        
                        各种树
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="2.1" data-path="树的实现/B-树.html">
            
                
                    <a href="../树的实现/B-树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.1.</b>
                        
                        B-树
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="树的实现/B+树.html">
            
                
                    <a href="../树的实现/B+树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.2.</b>
                        
                        B+树
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="树的实现/红黑树.html">
            
                
                    <a href="../树的实现/红黑树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.3.</b>
                        
                        红黑树
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="3" >
            
            <span><b>3.</b> 六大排序</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="3.1" data-path="六大排序/六大基本排序.html">
            
                
                    <a href="../六大排序/六大基本排序.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.1.</b>
                        
                        六大基本排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="六大排序/快速排序.html">
            
                
                    <a href="../六大排序/快速排序.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.2.</b>
                        
                        快速排序
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="4" >
            
            <span><b>4.</b> 算法的介绍</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="4.1" data-path="算法的介绍/字典序算法.html">
            
                
                    <a href="../算法的介绍/字典序算法.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.1.</b>
                        
                        字典序算法
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="算法的介绍/布隆算法.html">
            
                
                    <a href="../算法的介绍/布隆算法.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.2.</b>
                        
                        布隆算法
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    


            
            <li class="divider"></li>
            <li>
                <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
                    Published with GitBook
                </a>
            </li>
            
        </ul>
    </nav>
</div>

    <div class="book-body">
        <div class="body-inner">
            <div class="book-header" role="navigation">
    <!-- Actions Left -->
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="../" >python 数据结构与算法</a>
    </h1>
</div>

            <div class="page-wrapper" tabindex="-1" role="main">
                <div class="page-inner">
                
                
                    <section class="normal" id="section-">
                    
                        <h2 id="b&#x6811;">B&#x6811;</h2>
<p>&#x200B;       &#x5373;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF1A;</p>
<p>&#x200B;       1.&#x6240;&#x6709;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x81F3;&#x591A;&#x62E5;&#x6709;&#x4E24;&#x4E2A;&#x513F;&#x5B50;&#xFF08;Left&#x548C;Right&#xFF09;&#xFF1B;</p>
<p>&#x200B;       2.&#x6240;&#x6709;&#x7ED3;&#x70B9;&#x5B58;&#x50A8;&#x4E00;&#x4E2A;&#x5173;&#x952E;&#x5B57;&#xFF1B;</p>
<p>&#x200B;       3.&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x5DE6;&#x6307;&#x9488;&#x6307;&#x5411;&#x5C0F;&#x4E8E;&#x5176;&#x5173;&#x952E;&#x5B57;&#x7684;&#x5B50;&#x6811;&#xFF0C;&#x53F3;&#x6307;&#x9488;&#x6307;&#x5411;&#x5927;&#x4E8E;&#x5176;&#x5173;&#x952E;&#x5B57;&#x7684;&#x5B50;&#x6811;&#xFF1B;</p>
<p>&#x200B;       B&#x6811;&#x7684;&#x641C;&#x7D22;&#xFF0C;&#x4ECE;&#x6839;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#xFF0C;&#x5982;&#x679C;&#x67E5;&#x8BE2;&#x7684;&#x5173;&#x952E;&#x5B57;&#x4E0E;&#x7ED3;&#x70B9;&#x7684;&#x5173;&#x952E;&#x5B57;&#x76F8;&#x7B49;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x547D;&#x4E2D;&#xFF1B;</p>
<p>&#x5426;&#x5219;&#xFF0C;&#x5982;&#x679C;&#x67E5;&#x8BE2;&#x5173;&#x952E;&#x5B57;&#x6BD4;&#x7ED3;&#x70B9;&#x5173;&#x952E;&#x5B57;&#x5C0F;&#xFF0C;&#x5C31;&#x8FDB;&#x5165;&#x5DE6;&#x513F;&#x5B50;&#xFF1B;&#x5982;&#x679C;&#x6BD4;&#x7ED3;&#x70B9;&#x5173;&#x952E;&#x5B57;&#x5927;&#xFF0C;&#x5C31;&#x8FDB;&#x5165;</p>
<p>&#x53F3;&#x513F;&#x5B50;&#xFF1B;&#x5982;&#x679C;&#x5DE6;&#x513F;&#x5B50;&#x6216;&#x53F3;&#x513F;&#x5B50;&#x7684;&#x6307;&#x9488;&#x4E3A;&#x7A7A;&#xFF0C;&#x5219;&#x62A5;&#x544A;&#x627E;&#x4E0D;&#x5230;&#x76F8;&#x5E94;&#x7684;&#x5173;&#x952E;&#x5B57;&#xFF1B;</p>
<p>&#x200B;       &#x5982;&#x679C;B&#x6811;&#x7684;&#x6240;&#x6709;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x5DE6;&#x53F3;&#x5B50;&#x6811;&#x7684;&#x7ED3;&#x70B9;&#x6570;&#x76EE;&#x5747;&#x4FDD;&#x6301;&#x5DEE;&#x4E0D;&#x591A;&#xFF08;&#x5E73;&#x8861;&#xFF09;&#xFF0C;&#x90A3;&#x4E48;B&#x6811;</p>
<p>&#x7684;&#x641C;&#x7D22;&#x6027;&#x80FD;&#x903C;&#x8FD1;&#x4E8C;&#x5206;&#x67E5;&#x627E;&#xFF1B;&#x4F46;&#x5B83;&#x6BD4;&#x8FDE;&#x7EED;&#x5185;&#x5B58;&#x7A7A;&#x95F4;&#x7684;&#x4E8C;&#x5206;&#x67E5;&#x627E;&#x7684;&#x4F18;&#x70B9;&#x662F;&#xFF0C;&#x6539;&#x53D8;B&#x6811;&#x7ED3;&#x6784;</p>
<p>&#xFF08;&#x63D2;&#x5165;&#x4E0E;&#x5220;&#x9664;&#x7ED3;&#x70B9;&#xFF09;&#x4E0D;&#x9700;&#x8981;&#x79FB;&#x52A8;&#x5927;&#x6BB5;&#x7684;&#x5185;&#x5B58;&#x6570;&#x636E;&#xFF0C;&#x751A;&#x81F3;&#x901A;&#x5E38;&#x662F;&#x5E38;&#x6570;&#x5F00;&#x9500;&#xFF1B;</p>
<p>   &#x4F46;B&#x6811;&#x5728;&#x7ECF;&#x8FC7;&#x591A;&#x6B21;&#x63D2;&#x5165;&#x4E0E;&#x5220;&#x9664;&#x540E;&#xFF0C;&#x6709;&#x53EF;&#x80FD;&#x5BFC;&#x81F4;&#x4E0D;&#x540C;&#x7684;&#x7ED3;&#x6784;&#xFF1A;</p>
<p>   &#x53F3;&#x8FB9;&#x4E5F;&#x662F;&#x4E00;&#x4E2A;B&#x6811;&#xFF0C;&#x4F46;&#x5B83;&#x7684;&#x641C;&#x7D22;&#x6027;&#x80FD;&#x5DF2;&#x7ECF;&#x662F;&#x7EBF;&#x6027;&#x7684;&#x4E86;&#xFF1B;&#x540C;&#x6837;&#x7684;&#x5173;&#x952E;&#x5B57;&#x96C6;&#x5408;&#x6709;&#x53EF;&#x80FD;&#x5BFC;&#x81F4;&#x4E0D;&#x540C;&#x7684;</p>
<p>&#x6811;&#x7ED3;&#x6784;&#x7D22;&#x5F15;&#xFF1B;&#x6240;&#x4EE5;&#xFF0C;&#x4F7F;&#x7528;B&#x6811;&#x8FD8;&#x8981;&#x8003;&#x8651;&#x5C3D;&#x53EF;&#x80FD;&#x8BA9;B&#x6811;&#x4FDD;&#x6301;&#x5DE6;&#x56FE;&#x7684;&#x7ED3;&#x6784;&#xFF0C;&#x548C;&#x907F;&#x514D;&#x53F3;&#x56FE;&#x7684;&#x7ED3;&#x6784;&#xFF0C;&#x4E5F;&#x5C31;</p>
<p>&#x662F;&#x6240;&#x8C13;&#x7684;&#x201C;&#x5E73;&#x8861;&#x201D;&#x95EE;&#x9898;&#xFF1B;      </p>
<p>&#x200B;       &#x5B9E;&#x9645;&#x4F7F;&#x7528;&#x7684;B&#x6811;&#x90FD;&#x662F;&#x5728;&#x539F;B&#x6811;&#x7684;&#x57FA;&#x7840;&#x4E0A;&#x52A0;&#x4E0A;&#x5E73;&#x8861;&#x7B97;&#x6CD5;&#xFF0C;&#x5373;&#x201C;&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;&#x201D;&#xFF1B;&#x5982;&#x4F55;&#x4FDD;&#x6301;B&#x6811;</p>
<p>&#x7ED3;&#x70B9;&#x5206;&#x5E03;&#x5747;&#x5300;&#x7684;&#x5E73;&#x8861;&#x7B97;&#x6CD5;&#x662F;&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x5173;&#x952E;&#xFF1B;&#x5E73;&#x8861;&#x7B97;&#x6CD5;&#x662F;&#x4E00;&#x79CD;&#x5728;B&#x6811;&#x4E2D;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#x7ED3;&#x70B9;&#x7684;</p>
<p>&#x7B56;&#x7565;&#xFF1B;</p>
<hr>
<h2 id="b&#x6811;">B-&#x6811;</h2>
<p>&#x200B;       &#x662F;&#x4E00;&#x79CD;&#x591A;&#x8DEF;&#x641C;&#x7D22;&#x6811;&#xFF08;&#x5E76;&#x4E0D;&#x662F;&#x4E8C;&#x53C9;&#x7684;&#xFF09;&#xFF1A;</p>
<p>&#x200B;       1.&#x5B9A;&#x4E49;&#x4EFB;&#x610F;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x6700;&#x591A;&#x53EA;&#x6709;M&#x4E2A;&#x513F;&#x5B50;&#xFF1B;&#x4E14;M&gt;2&#xFF1B;</p>
<p>&#x200B;       2.&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x513F;&#x5B50;&#x6570;&#x4E3A;[2, M]&#xFF1B;</p>
<p>&#x200B;       3.&#x9664;&#x6839;&#x7ED3;&#x70B9;&#x4EE5;&#x5916;&#x7684;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x513F;&#x5B50;&#x6570;&#x4E3A;[M/2, M]&#xFF1B;</p>
<p>&#x200B;       4.&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x5B58;&#x653E;&#x81F3;&#x5C11;M/2-1&#xFF08;&#x53D6;&#x4E0A;&#x6574;&#xFF09;&#x548C;&#x81F3;&#x591A;M-1&#x4E2A;&#x5173;&#x952E;&#x5B57;&#xFF1B;&#xFF08;&#x81F3;&#x5C11;2&#x4E2A;&#x5173;&#x952E;&#x5B57;&#xFF09;</p>
<p>&#x200B;       5.&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x5173;&#x952E;&#x5B57;&#x4E2A;&#x6570;=&#x6307;&#x5411;&#x513F;&#x5B50;&#x7684;&#x6307;&#x9488;&#x4E2A;&#x6570;-1&#xFF1B;</p>
<p>&#x200B;       6.&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x5173;&#x952E;&#x5B57;&#xFF1A;K[1], K[2], &#x2026;, K[M-1]&#xFF1B;&#x4E14;K[i] &lt; K[i+1]&#xFF1B;</p>
<p>&#x200B;       7.&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x6307;&#x9488;&#xFF1A;P[1], P[2], &#x2026;, P[M]&#xFF1B;&#x5176;&#x4E2D;P[1]&#x6307;&#x5411;&#x5173;&#x952E;&#x5B57;&#x5C0F;&#x4E8E;K[1]&#x7684;</p>
<p>&#x5B50;&#x6811;&#xFF0C;P[M]&#x6307;&#x5411;&#x5173;&#x952E;&#x5B57;&#x5927;&#x4E8E;K[M-1]&#x7684;&#x5B50;&#x6811;&#xFF0C;&#x5176;&#x5B83;P[i]&#x6307;&#x5411;&#x5173;&#x952E;&#x5B57;&#x5C5E;&#x4E8E;(K[i-1], K[i])&#x7684;&#x5B50;&#x6811;&#xFF1B;</p>
<p>&#x200B;       8.&#x6240;&#x6709;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x4F4D;&#x4E8E;&#x540C;&#x4E00;&#x5C42;&#xFF1B;</p>
<p>&#x200B;       &#x5982;&#xFF1A;&#xFF08;M=3&#xFF09;</p>
<p>&#x200B;       B-&#x6811;&#x7684;&#x641C;&#x7D22;&#xFF0C;&#x4ECE;&#x6839;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#xFF0C;&#x5BF9;&#x7ED3;&#x70B9;&#x5185;&#x7684;&#x5173;&#x952E;&#x5B57;&#xFF08;&#x6709;&#x5E8F;&#xFF09;&#x5E8F;&#x5217;&#x8FDB;&#x884C;&#x4E8C;&#x5206;&#x67E5;&#x627E;&#xFF0C;&#x5982;&#x679C;</p>
<p>&#x547D;&#x4E2D;&#x5219;&#x7ED3;&#x675F;&#xFF0C;&#x5426;&#x5219;&#x8FDB;&#x5165;&#x67E5;&#x8BE2;&#x5173;&#x952E;&#x5B57;&#x6240;&#x5C5E;&#x8303;&#x56F4;&#x7684;&#x513F;&#x5B50;&#x7ED3;&#x70B9;&#xFF1B;&#x91CD;&#x590D;&#xFF0C;&#x76F4;&#x5230;&#x6240;&#x5BF9;&#x5E94;&#x7684;&#x513F;&#x5B50;&#x6307;&#x9488;&#x4E3A;</p>
<p>&#x7A7A;&#xFF0C;&#x6216;&#x5DF2;&#x7ECF;&#x662F;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#xFF1B;</p>
<p>B-&#x6811;&#x7684;&#x7279;&#x6027;&#xFF1A;</p>
<p>&#x200B;       1.&#x5173;&#x952E;&#x5B57;&#x96C6;&#x5408;&#x5206;&#x5E03;&#x5728;&#x6574;&#x9897;&#x6811;&#x4E2D;&#xFF1B;</p>
<p>&#x200B;       2.&#x4EFB;&#x4F55;&#x4E00;&#x4E2A;&#x5173;&#x952E;&#x5B57;&#x51FA;&#x73B0;&#x4E14;&#x53EA;&#x51FA;&#x73B0;&#x5728;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x4E2D;&#xFF1B;</p>
<p>&#x200B;       3.&#x641C;&#x7D22;&#x6709;&#x53EF;&#x80FD;&#x5728;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7ED3;&#x675F;&#xFF1B;</p>
<p>&#x200B;       4.&#x5176;&#x641C;&#x7D22;&#x6027;&#x80FD;&#x7B49;&#x4EF7;&#x4E8E;&#x5728;&#x5173;&#x952E;&#x5B57;&#x5168;&#x96C6;&#x5185;&#x505A;&#x4E00;&#x6B21;&#x4E8C;&#x5206;&#x67E5;&#x627E;&#xFF1B;</p>
<p>&#x200B;       5.&#x81EA;&#x52A8;&#x5C42;&#x6B21;&#x63A7;&#x5236;&#xFF1B;</p>
<p>&#x200B;       &#x7531;&#x4E8E;&#x9650;&#x5236;&#x4E86;&#x9664;&#x6839;&#x7ED3;&#x70B9;&#x4EE5;&#x5916;&#x7684;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#xFF0C;&#x81F3;&#x5C11;&#x542B;&#x6709;M/2&#x4E2A;&#x513F;&#x5B50;&#xFF0C;&#x786E;&#x4FDD;&#x4E86;&#x7ED3;&#x70B9;&#x7684;&#x81F3;&#x5C11;</p>
<p>&#x5229;&#x7528;&#x7387;&#xFF0C;&#x5176;&#x6700;&#x5E95;&#x641C;&#x7D22;&#x6027;&#x80FD;&#x4E3A;&#xFF1A;</p>
<p>&#x200B;       &#x5176;&#x4E2D;&#xFF0C;M&#x4E3A;&#x8BBE;&#x5B9A;&#x7684;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x6700;&#x591A;&#x5B50;&#x6811;&#x4E2A;&#x6570;&#xFF0C;N&#x4E3A;&#x5173;&#x952E;&#x5B57;&#x603B;&#x6570;&#xFF1B;</p>
<p>&#x200B;       &#x6240;&#x4EE5;B-&#x6811;&#x7684;&#x6027;&#x80FD;&#x603B;&#x662F;&#x7B49;&#x4EF7;&#x4E8E;&#x4E8C;&#x5206;&#x67E5;&#x627E;&#xFF08;&#x4E0E;M&#x503C;&#x65E0;&#x5173;&#xFF09;&#xFF0C;&#x4E5F;&#x5C31;&#x6CA1;&#x6709;B&#x6811;&#x5E73;&#x8861;&#x7684;&#x95EE;&#x9898;&#xFF1B;</p>
<p>&#x200B;       &#x7531;&#x4E8E;M/2&#x7684;&#x9650;&#x5236;&#xFF0C;&#x5728;&#x63D2;&#x5165;&#x7ED3;&#x70B9;&#x65F6;&#xFF0C;&#x5982;&#x679C;&#x7ED3;&#x70B9;&#x5DF2;&#x6EE1;&#xFF0C;&#x9700;&#x8981;&#x5C06;&#x7ED3;&#x70B9;&#x5206;&#x88C2;&#x4E3A;&#x4E24;&#x4E2A;&#x5404;&#x5360;</p>
<p>M/2&#x7684;&#x7ED3;&#x70B9;&#xFF1B;&#x5220;&#x9664;&#x7ED3;&#x70B9;&#x65F6;&#xFF0C;&#x9700;&#x5C06;&#x4E24;&#x4E2A;&#x4E0D;&#x8DB3;M/2&#x7684;&#x5144;&#x5F1F;&#x7ED3;&#x70B9;&#x5408;&#x5E76;&#xFF1B;</p>
<h2 id="b&#x6811;">B+&#x6811;</h2>
<p>&#x200B;       B+&#x6811;&#x662F;B-&#x6811;&#x7684;&#x53D8;&#x4F53;&#xFF0C;&#x4E5F;&#x662F;&#x4E00;&#x79CD;&#x591A;&#x8DEF;&#x641C;&#x7D22;&#x6811;&#xFF1A;</p>
<p>&#x200B;       1.&#x5176;&#x5B9A;&#x4E49;&#x57FA;&#x672C;&#x4E0E;B-&#x6811;&#x540C;&#xFF0C;&#x9664;&#x4E86;&#xFF1A;</p>
<p>&#x200B;       2.&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x5B50;&#x6811;&#x6307;&#x9488;&#x4E0E;&#x5173;&#x952E;&#x5B57;&#x4E2A;&#x6570;&#x76F8;&#x540C;&#xFF1B;</p>
<p>&#x200B;       3.&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x5B50;&#x6811;&#x6307;&#x9488;P[i]&#xFF0C;&#x6307;&#x5411;&#x5173;&#x952E;&#x5B57;&#x503C;&#x5C5E;&#x4E8E;[K[i], K[i+1])&#x7684;&#x5B50;&#x6811;</p>
<p>&#xFF08;B-&#x6811;&#x662F;&#x5F00;&#x533A;&#x95F4;&#xFF09;&#xFF1B;</p>
<p>&#x200B;       5.&#x4E3A;&#x6240;&#x6709;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x589E;&#x52A0;&#x4E00;&#x4E2A;&#x94FE;&#x6307;&#x9488;&#xFF1B;</p>
<p>&#x200B;       6.&#x6240;&#x6709;&#x5173;&#x952E;&#x5B57;&#x90FD;&#x5728;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x51FA;&#x73B0;&#xFF1B;</p>
<p>&#x200B;       &#x5982;&#xFF1A;&#xFF08;M=3&#xFF09;</p>
<p>   B+&#x7684;&#x641C;&#x7D22;&#x4E0E;B-&#x6811;&#x4E5F;&#x57FA;&#x672C;&#x76F8;&#x540C;&#xFF0C;&#x533A;&#x522B;&#x662F;B+&#x6811;&#x53EA;&#x6709;&#x8FBE;&#x5230;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x624D;&#x547D;&#x4E2D;&#xFF08;B-&#x6811;&#x53EF;&#x4EE5;&#x5728;</p>
<p>&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x547D;&#x4E2D;&#xFF09;&#xFF0C;&#x5176;&#x6027;&#x80FD;&#x4E5F;&#x7B49;&#x4EF7;&#x4E8E;&#x5728;&#x5173;&#x952E;&#x5B57;&#x5168;&#x96C6;&#x505A;&#x4E00;&#x6B21;&#x4E8C;&#x5206;&#x67E5;&#x627E;&#xFF1B;</p>
<p>&#x200B;       B+&#x7684;&#x7279;&#x6027;&#xFF1A;</p>
<p>&#x200B;       1.&#x6240;&#x6709;&#x5173;&#x952E;&#x5B57;&#x90FD;&#x51FA;&#x73B0;&#x5728;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x94FE;&#x8868;&#x4E2D;&#xFF08;&#x7A20;&#x5BC6;&#x7D22;&#x5F15;&#xFF09;&#xFF0C;&#x4E14;&#x94FE;&#x8868;&#x4E2D;&#x7684;&#x5173;&#x952E;&#x5B57;&#x6070;&#x597D;</p>
<p>&#x662F;&#x6709;&#x5E8F;&#x7684;&#xFF1B;</p>
<p>&#x200B;       2.&#x4E0D;&#x53EF;&#x80FD;&#x5728;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x547D;&#x4E2D;&#xFF1B;</p>
<p>&#x200B;       3.&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x76F8;&#x5F53;&#x4E8E;&#x662F;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x7D22;&#x5F15;&#xFF08;&#x7A00;&#x758F;&#x7D22;&#x5F15;&#xFF09;&#xFF0C;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x76F8;&#x5F53;&#x4E8E;&#x662F;&#x5B58;&#x50A8;</p>
<p>&#xFF08;&#x5173;&#x952E;&#x5B57;&#xFF09;&#x6570;&#x636E;&#x7684;&#x6570;&#x636E;&#x5C42;&#xFF1B;</p>
<p>&#x200B;       4.&#x66F4;&#x9002;&#x5408;&#x6587;&#x4EF6;&#x7D22;&#x5F15;&#x7CFB;&#x7EDF;&#xFF1B;</p>
<hr>
<h2 id="b&#x6811;">B*&#x6811;</h2>
<p>&#x200B;       &#x662F;B+&#x6811;&#x7684;&#x53D8;&#x4F53;&#xFF0C;&#x5728;B+&#x6811;&#x7684;&#x975E;&#x6839;&#x548C;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x518D;&#x589E;&#x52A0;&#x6307;&#x5411;&#x5144;&#x5F1F;&#x7684;&#x6307;&#x9488;&#xFF1B;</p>
<p>   B<em>&#x6811;&#x5B9A;&#x4E49;&#x4E86;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x5173;&#x952E;&#x5B57;&#x4E2A;&#x6570;&#x81F3;&#x5C11;&#x4E3A;(2/3)</em>M&#xFF0C;&#x5373;&#x5757;&#x7684;&#x6700;&#x4F4E;&#x4F7F;&#x7528;&#x7387;&#x4E3A;2/3</p>
<p>&#xFF08;&#x4EE3;&#x66FF;B+&#x6811;&#x7684;1/2&#xFF09;&#xFF1B;</p>
<p>&#x200B;       B+&#x6811;&#x7684;&#x5206;&#x88C2;&#xFF1A;&#x5F53;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x6EE1;&#x65F6;&#xFF0C;&#x5206;&#x914D;&#x4E00;&#x4E2A;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#xFF0C;&#x5E76;&#x5C06;&#x539F;&#x7ED3;&#x70B9;&#x4E2D;1/2&#x7684;&#x6570;&#x636E;</p>
<p>&#x590D;&#x5236;&#x5230;&#x65B0;&#x7ED3;&#x70B9;&#xFF0C;&#x6700;&#x540E;&#x5728;&#x7236;&#x7ED3;&#x70B9;&#x4E2D;&#x589E;&#x52A0;&#x65B0;&#x7ED3;&#x70B9;&#x7684;&#x6307;&#x9488;&#xFF1B;B+&#x6811;&#x7684;&#x5206;&#x88C2;&#x53EA;&#x5F71;&#x54CD;&#x539F;&#x7ED3;&#x70B9;&#x548C;&#x7236;</p>
<p>&#x7ED3;&#x70B9;&#xFF0C;&#x800C;&#x4E0D;&#x4F1A;&#x5F71;&#x54CD;&#x5144;&#x5F1F;&#x7ED3;&#x70B9;&#xFF0C;&#x6240;&#x4EE5;&#x5B83;&#x4E0D;&#x9700;&#x8981;&#x6307;&#x5411;&#x5144;&#x5F1F;&#x7684;&#x6307;&#x9488;&#xFF1B;</p>
<p>&#x200B;       B*&#x6811;&#x7684;&#x5206;&#x88C2;&#xFF1A;&#x5F53;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;&#x6EE1;&#x65F6;&#xFF0C;&#x5982;&#x679C;&#x5B83;&#x7684;&#x4E0B;&#x4E00;&#x4E2A;&#x5144;&#x5F1F;&#x7ED3;&#x70B9;&#x672A;&#x6EE1;&#xFF0C;&#x90A3;&#x4E48;&#x5C06;&#x4E00;&#x90E8;&#x5206;</p>
<p>&#x6570;&#x636E;&#x79FB;&#x5230;&#x5144;&#x5F1F;&#x7ED3;&#x70B9;&#x4E2D;&#xFF0C;&#x518D;&#x5728;&#x539F;&#x7ED3;&#x70B9;&#x63D2;&#x5165;&#x5173;&#x952E;&#x5B57;&#xFF0C;&#x6700;&#x540E;&#x4FEE;&#x6539;&#x7236;&#x7ED3;&#x70B9;&#x4E2D;&#x5144;&#x5F1F;&#x7ED3;&#x70B9;&#x7684;&#x5173;&#x952E;&#x5B57;</p>
<p>&#xFF08;&#x56E0;&#x4E3A;&#x5144;&#x5F1F;&#x7ED3;&#x70B9;&#x7684;&#x5173;&#x952E;&#x5B57;&#x8303;&#x56F4;&#x6539;&#x53D8;&#x4E86;&#xFF09;&#xFF1B;&#x5982;&#x679C;&#x5144;&#x5F1F;&#x4E5F;&#x6EE1;&#x4E86;&#xFF0C;&#x5219;&#x5728;&#x539F;&#x7ED3;&#x70B9;&#x4E0E;&#x5144;&#x5F1F;&#x7ED3;&#x70B9;&#x4E4B;</p>
<p>&#x95F4;&#x589E;&#x52A0;&#x65B0;&#x7ED3;&#x70B9;&#xFF0C;&#x5E76;&#x5404;&#x590D;&#x5236;1/3&#x7684;&#x6570;&#x636E;&#x5230;&#x65B0;&#x7ED3;&#x70B9;&#xFF0C;&#x6700;&#x540E;&#x5728;&#x7236;&#x7ED3;&#x70B9;&#x589E;&#x52A0;&#x65B0;&#x7ED3;&#x70B9;&#x7684;&#x6307;&#x9488;&#xFF1B;</p>
<p>&#x200B;       &#x6240;&#x4EE5;&#xFF0C;B*&#x6811;&#x5206;&#x914D;&#x65B0;&#x7ED3;&#x70B9;&#x7684;&#x6982;&#x7387;&#x6BD4;B+&#x6811;&#x8981;&#x4F4E;&#xFF0C;&#x7A7A;&#x95F4;&#x4F7F;&#x7528;&#x7387;&#x66F4;&#x9AD8;&#xFF1B;</p>
<h2 id="&#x7EA2;&#x9ED1;&#x6811;">&#x7EA2;&#x9ED1;&#x6811;</h2>
<p>&#x200B;     &#x7EA2;&#x9ED1;&#x6811;&#xFF08;Red-Black Tree&#xFF09;&#x662F;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF08;Binary Search Tree&#xFF09;&#x7684;&#x4E00;&#x79CD;&#x6539;&#x8FDB;&#x3002;&#x6211;&#x4EEC;&#x77E5;&#x9053;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5728;&#x6700;&#x574F;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#x53EF;&#x80FD;&#x4F1A;&#x53D8;&#x6210;&#x4E00;&#x4E2A;&#x94FE;&#x8868;&#xFF08;&#x5F53;&#x6240;&#x6709;&#x8282;&#x70B9;&#x6309;&#x4ECE;&#x5C0F;&#x5230;&#x5927;&#x7684;&#x987A;&#x5E8F;&#x4F9D;&#x6B21;&#x63D2;&#x5165;&#x540E;&#xFF09;&#x3002;&#x800C;&#x7EA2;&#x9ED1;&#x6811;&#x5728;&#x6BCF;&#x4E00;&#x6B21;&#x63D2;&#x5165;&#x6216;&#x5220;&#x9664;&#x8282;&#x70B9;&#x4E4B;&#x540E;&#x90FD;&#x4F1A;&#x82B1;O&#xFF08;log N&#xFF09;&#x7684;&#x65F6;&#x95F4;&#x6765;&#x5BF9;&#x6811;&#x7684;&#x7ED3;&#x6784;&#x4F5C;&#x4FEE;&#x6539;&#xFF0C;&#x4EE5;&#x4FDD;&#x6301;&#x6811;&#x7684;&#x5E73;&#x8861;&#x3002;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;&#xFF0C;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x67E5;&#x627E;&#x65B9;&#x6CD5;&#x4E0E;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5B8C;&#x5168;&#x4E00;&#x6837;&#xFF1B;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#x8282;&#x70B9;&#x7684;&#x7684;&#x65B9;&#x6CD5;&#x524D;&#x534A;&#x90E8;&#x5206;&#x8282;&#x4E0E;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x5B8C;&#x5168;&#x4E00;&#x6837;&#xFF0C;&#x800C;&#x540E;&#x534A;&#x90E8;&#x5206;&#x6DFB;&#x52A0;&#x4E86;&#x4E00;&#x4E9B;&#x4FEE;&#x6539;&#x6811;&#x7684;&#x7ED3;&#x6784;&#x7684;&#x64CD;&#x4F5C;&#x3002;</p>
<p>&#x200B;     &#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x4E0A;&#x7684;&#x5C5E;&#x6027;&#x9664;&#x4E86;&#x6709;&#x4E00;&#x4E2A;key&#x3001;3&#x4E2A;&#x6307;&#x9488;&#xFF1A;parent&#x3001;lchild&#x3001;rchild&#x4EE5;&#x5916;&#xFF0C;&#x8FD8;&#x591A;&#x4E86;&#x4E00;&#x4E2A;&#x5C5E;&#x6027;&#xFF1A;color&#x3002;&#x5B83;&#x53EA;&#x80FD;&#x662F;&#x4E24;&#x79CD;&#x989C;&#x8272;&#xFF1A;&#x7EA2;&#x6216;&#x9ED1;&#x3002;&#x800C;&#x7EA2;&#x9ED1;&#x6811;&#x9664;&#x4E86;&#x5177;&#x6709;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x6240;&#x6709;&#x6027;&#x8D28;&#x4E4B;&#x5916;&#xFF0C;&#x8FD8;&#x5177;&#x6709;&#x4EE5;&#x4E0B;4&#x70B9;&#x6027;&#x8D28;&#xFF1A;
\1. &#x6839;&#x8282;&#x70B9;&#x662F;&#x9ED1;&#x8272;&#x7684;&#x3002;
\2. &#x7A7A;&#x8282;&#x70B9;&#x662F;&#x9ED1;&#x8272;&#x7684;&#xFF08;&#x7EA2;&#x9ED1;&#x6811;&#x4E2D;&#xFF0C;&#x6839;&#x8282;&#x70B9;&#x7684;parent&#x4EE5;&#x53CA;&#x6240;&#x6709;&#x53F6;&#x8282;&#x70B9;lchild&#x3001;rchild&#x90FD;&#x4E0D;&#x6307;&#x5411;NULL&#xFF0C;&#x800C;&#x662F;&#x6307;&#x5411;&#x4E00;&#x4E2A;&#x5B9A;&#x4E49;&#x597D;&#x7684;&#x7A7A;&#x8282;&#x70B9;&#xFF09;&#x3002;
\3. &#x7EA2;&#x8272;&#x8282;&#x70B9;&#x7684;&#x7236;&#x3001;&#x5DE6;&#x5B50;&#x3001;&#x53F3;&#x5B50;&#x8282;&#x70B9;&#x90FD;&#x662F;&#x9ED1;&#x8272;&#x3002;
\4. &#x5728;&#x4EFB;&#x4F55;&#x4E00;&#x68F5;&#x5B50;&#x6811;&#x4E2D;&#xFF0C;&#x6BCF;&#x4E00;&#x6761;&#x4ECE;&#x6839;&#x8282;&#x70B9;&#x5411;&#x4E0B;&#x8D70;&#x5230;&#x7A7A;&#x8282;&#x70B9;&#x7684;&#x8DEF;&#x5F84;&#x4E0A;&#x5305;&#x542B;&#x7684;&#x9ED1;&#x8272;&#x8282;&#x70B9;&#x6570;&#x91CF;&#x90FD;&#x76F8;&#x540C;&#x3002;</p>
<hr>
<h2 id="&#x5C0F;&#x7ED3;">&#x5C0F;&#x7ED3;</h2>
<p>&#x200B;       B&#x6811;&#xFF1A;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x53EA;&#x5B58;&#x50A8;&#x4E00;&#x4E2A;&#x5173;&#x952E;&#x5B57;&#xFF0C;&#x7B49;&#x4E8E;&#x5219;&#x547D;&#x4E2D;&#xFF0C;&#x5C0F;&#x4E8E;&#x8D70;&#x5DE6;&#x7ED3;&#x70B9;&#xFF0C;&#x5927;&#x4E8E;</p>
<p>&#x8D70;&#x53F3;&#x7ED3;&#x70B9;&#xFF1B;</p>
<p>&#x200B;       B-&#x6811;&#xFF1A;&#x591A;&#x8DEF;&#x641C;&#x7D22;&#x6811;&#xFF0C;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x5B58;&#x50A8;M/2&#x5230;M&#x4E2A;&#x5173;&#x952E;&#x5B57;&#xFF0C;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x5B58;&#x50A8;&#x6307;&#x5411;&#x5173;&#x952E;</p>
<p>&#x5B57;&#x8303;&#x56F4;&#x7684;&#x5B50;&#x7ED3;&#x70B9;&#xFF1B;</p>
<p>&#x200B;       &#x6240;&#x6709;&#x5173;&#x952E;&#x5B57;&#x5728;&#x6574;&#x9897;&#x6811;&#x4E2D;&#x51FA;&#x73B0;&#xFF0C;&#x4E14;&#x53EA;&#x51FA;&#x73B0;&#x4E00;&#x6B21;&#xFF0C;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x53EF;&#x4EE5;&#x547D;&#x4E2D;&#xFF1B;</p>
<p>&#x200B;       B+&#x6811;&#xFF1A;&#x5728;B-&#x6811;&#x57FA;&#x7840;&#x4E0A;&#xFF0C;&#x4E3A;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x589E;&#x52A0;&#x94FE;&#x8868;&#x6307;&#x9488;&#xFF0C;&#x6240;&#x6709;&#x5173;&#x952E;&#x5B57;&#x90FD;&#x5728;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;</p>
<p>&#x4E2D;&#x51FA;&#x73B0;&#xFF0C;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x4F5C;&#x4E3A;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x7D22;&#x5F15;&#xFF1B;B+&#x6811;&#x603B;&#x662F;&#x5230;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x624D;&#x547D;&#x4E2D;&#xFF1B;</p>
<p>&#x200B;       B*&#x6811;&#xFF1A;&#x5728;B+&#x6811;&#x57FA;&#x7840;&#x4E0A;&#xFF0C;&#x4E3A;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x4E5F;&#x589E;&#x52A0;&#x94FE;&#x8868;&#x6307;&#x9488;&#xFF0C;&#x5C06;&#x7ED3;&#x70B9;&#x7684;&#x6700;&#x4F4E;&#x5229;&#x7528;&#x7387;</p>
<p>&#x4ECE;1/2&#x63D0;&#x9AD8;&#x5230;2/3&#xFF1B;</p>
<hr>

                    
                    </section>
                
                
                </div>
            </div>
        </div>

        
        <a href="../剑指offer/剑指offer25-43题.html" class="navigation navigation-prev " aria-label="Previous page: 剑指offer25-43题"><i class="fa fa-angle-left"></i></a>
        
        
        <a href="../树的实现/B-树.html" class="navigation navigation-next " aria-label="Next page: B-树"><i class="fa fa-angle-right"></i></a>
        
    </div>
</div>

        
<script src="../gitbook/app.js"></script>

    
    <script src="../gitbook/plugins/gitbook-plugin-search/lunr.min.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-search/search.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-sharing/buttons.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-fontsettings/buttons.js"></script>
    

<script>
require(["gitbook"], function(gitbook) {
    var config = {"highlight":{},"search":{"maxIndexSize":1000000},"sharing":{"facebook":true,"twitter":true,"google":false,"weibo":false,"instapaper":false,"vk":false,"all":["facebook","google","twitter","weibo","instapaper"]},"fontsettings":{"theme":"white","family":"sans","size":2}};
    gitbook.start(config);
});
</script>

        
    </body>
    
</html>
